package com.java.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 哈夫曼树
 * @author 19252
 * @date 2020/7/26
 */
public class HuffmanTree {

    public static void main(String[] args) {
        HuffmanTree huffmanTree = new HuffmanTree();
        int[] array = new int[]{13, 7, 8, 3, 29, 6, 1};
        HuffmanNode huffmanNode = huffmanTree.createHuffmanTree(array);
        System.out.println(huffmanNode.getWight());
        huffmanNode.preOrder();
    }

    /**
     * 传入一个数组创建一个哈夫曼树
     * @param array 传入的数组
     */
    public HuffmanNode createHuffmanTree(int[] array){
        // 1.遍历数组，将数组元素构建为 HuffmanNode，并将每个节点存入List中
        List<HuffmanNode> huffmanNodes = new ArrayList<>();
        for (int value : array) {
            huffmanNodes.add(new HuffmanNode(value));
        }
        // 2.对每个结点进行比较按从小到大的顺序排序
        Collections.sort(huffmanNodes);
        // 3.进行哈夫曼树的拼接
        int size = huffmanNodes.size();
        HuffmanNode left;
        HuffmanNode right;
        while (huffmanNodes.size() > 1) {
            int i = 0;
            // 4.使用已经排好序的 list 中 权重最小的两个结点创建一个新的子树
            left = huffmanNodes.get(i);
            right = huffmanNodes.get(i + 1);
            // 为二叉树的根结点设置权重
            HuffmanNode parent = new HuffmanNode(left.getWight() + right.getWight());
            // 生成新的二叉树
            parent.setLeft(left);
            parent.setRight(right);
            // 将两个使用过的结点移除 list
            huffmanNodes.remove(left);
            huffmanNodes.remove(right);
            // 将新生成的二叉树添加进入list
            huffmanNodes.add(parent);
            // 添加重新生成的树时，可能会打乱顺序，需要重新排序
            Collections.sort(huffmanNodes);
            // 再重复的完成上面的操作
            // 直至完成哈夫曼树的生成即 list 中只剩一个数据
        }
        return huffmanNodes.get(0);
    }
}

/**
 * 哈夫曼树的结点
 */
class HuffmanNode implements Comparable<HuffmanNode>{

    /**
     * 结点的权重
     */
    private int wight;
    /**
     * 结点的左指针
     */
    private HuffmanNode left;
    /**
     * 结点的右指针
     */
    private HuffmanNode right;

    public HuffmanNode() {
    }

    public HuffmanNode(int wight) {
        this.wight = wight;
    }

    public int getWight() {
        return wight;
    }

    public void setWight(int wight) {
        this.wight = wight;
    }

    public HuffmanNode getLeft() {
        return left;
    }

    public void setLeft(HuffmanNode left) {
        this.left = left;
    }

    public HuffmanNode getRight() {
        return right;
    }

    public void setRight(HuffmanNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HuffmanNode{" +
                "wight=" + wight +
                '}';
    }

    @Override
    public int compareTo(HuffmanNode huffmanNode) {
        // 负数 this 小于 huffmanNode
        // 0 this 等于 huffmanNode
        // 正数 this 大于 huffmanNode
        return this.wight - huffmanNode.wight;
    }

    /**
     * 前序遍历
     */
    public void preOrder(){
        System.out.println(this.getWight());
        if (this.getLeft() != null){
            this.getLeft().preOrder();
        }
        if (this.getRight() != null){
            this.getRight().preOrder();
        }
    }
}